package main

import "fmt"

func main() {
	//获得一个数组
	numbers := []int{5, 7, 1, 3, 0, 2, 6, 9, 4, 8} //utils.GetRandSlices(10, 5)
	length := len(numbers)
	fmt.Printf("获取到 %d 一个元素数组：\n%v\n", length, numbers)
	//开始排序
	//将数据插入一个已经`排好序的序列`里边，并更具其大小插入到合适的位置，直到所有数列插入完成。插入时一排好序数据需要按照条件向后移动，为插入数据保留空间。
	for i := 1; i < length; i++ {
		//当前位置
		insertLeft := 0           //已排序最左边位置
		insertRight := i - 1      //已排序最右边位置
		insertIndex := insertLeft //默认插入首位
		tmp := numbers[i]
		//开始查找位置
		if tmp > numbers[insertLeft] && tmp < numbers[insertRight] {
			//在区间内，才有查找价值
			for insertLeft <= insertRight {
				mid := (insertRight + insertLeft) / 2
				if tmp < numbers[mid] {
					insertRight = mid - 1
				} else {
					insertLeft = mid + 1
				}
			}
			insertIndex = insertLeft
		} else if tmp >= numbers[insertRight] {
			insertIndex = insertRight + 1
		}

		//需要挪动位置，与i相等不需要动。
		if insertIndex < i {
			for j := i - 1; j >= insertLeft; j-- {
				numbers[j+1] = numbers[j]
			}
			numbers[insertLeft] = tmp
		}

		fmt.Printf("第 %d 次，获取到插入位置：%d ，插入数据：%d\n\n%v\n\n", i, insertIndex, numbers[insertIndex], numbers)
	}
	fmt.Printf("\n%v ", numbers)
}
